Линейное программирование

Линейное программирование — математическая дисциплина, посвящённая теории и методам решения экстремальных задач на множествах [math]\displaystyle{ n }[/math]-мерного векторного пространства, задаваемых системами линейных уравнений и неравенств.

Линейное программирование (ЛП) является частным случаем выпуклого программирования, которое в свою очередь является частным случаем математического программирования. Одновременно оно — основа нескольких методов решения задач целочисленного и нелинейного программирования. Одним из обобщений линейного программирования является дробно-линейное программирование.

Многие свойства задач линейного программирования можно интерпретировать также как свойства многогранников и таким образом геометрически формулировать и доказывать их.

История

Математические исследования отдельных экономических проблем, математическая формализация числового материала проводилась ещё в XIX веке. При математическом анализе процесса расширенного производства использовались алгебраические соотношения, анализ их проводился с помощью дифференциального исчисления. Это давало возможность получить общее представление о проблеме.

Развитие экономики потребовало количественных показателей, и в 1920 годы был создан межотраслевой баланс (МОБ). Он-то и послужил толчком в деле создания и исследования математических моделей. Разработка МОБ в 1924—1925 годах в СССР повлияла на работы экономиста и статистика Василия Васильевича Леонтьева. Он разработал межотраслевую модель производства и распределения продукции.

В 1938 году Леонид Витальевич Канторович в порядке научной консультации приступил к изучению чисто практической задачи по составлению наилучшего плана загрузки лущильных станков (фанерный трест). Эта задача не поддавалась обычным методам. Стало ясно, что задача не случайная.

В 1939 году Леонид Канторович опубликовал работу «Математические методы организации и планирования производства», в которой сформулировал новый класс экстремальных задач с ограничениями и разработал эффективный метод их решения, таким образом были заложены основы линейного программирования.

Изучение подобных задач привело к созданию новой научной дисциплины линейного программирования и открыло новый этап в развитии экономико-математических методов.

В 1949 году американский математик Джордж Бернард Данциг разработал эффективный метод решения задач линейного программирования (ЗЛП) — симплекс-метод.

Термин «программирование» нужно понимать в смысле «планирования» (один из переводов англ. programming). Он был предложен в середине 1940-х годов Джорджем Данцигом, одним из основателей линейного программирования, ещё до того, как компьютеры были использованы для решения линейных задач оптимизации.

Метод внутренних точек был впервые упомянут И. И. Дикиным в 1967 году.. Эти исследования были продолжены в том числе и отечественными учёными. В 1970-е годы В. Г. Жадану удалось получить основные результаты и разработать общий подход к построению методов внутренней точки для решения задач линейного и нелинейного программирования, основанный на преобразовании пространств; предложить барьерно-проективные и барьерно-ньютоновские численные методы.

Задачи

Общей (стандартной) задачей линейного программирования называется задача нахождения минимума линейной целевой функции (линейной формы) вида:

[math]\displaystyle{ f(x)=\sum_{j=1}^n c_jx_j=c_1x_1+c_2x_2+\ldots+c_nx_n. }[/math]

Задача, в которой фигурируют ограничения в форме неравенств, называется основной задачей линейного программирования (ОЗЛП)

[math]\displaystyle{ \sum_{j=1}^n a_{ij}x_j\geqslant b_i,\quad(i=1,\;2,\;\ldots,\;m) }[/math]

[math]\displaystyle{ x_j\geqslant 0.\quad(j=1,\;2,\;\ldots,\;n) }[/math]

Задача линейного программирования будет иметь канонический вид, если в основной задаче вместо первой системы неравенств имеет место система уравнений с ограничениями в форме равенства:

[math]\displaystyle{ \sum_{j=1}^n a_{ij}x_j=b_i.\quad (i=1,\;2,\;\ldots,\;m) }[/math]

Основную задачу можно свести к канонической путём введения дополнительных переменных.

Задачи линейного программирования наиболее общего вида (задачи со смешанными ограничениями: равенствами и неравенствами, наличием переменных, свободных от ограничений) могут быть приведены к эквивалентным (имеющим то же множество решений) заменами переменных и заменой равенств на пару неравенств.

Легко заметить, что задачу нахождения максимума можно заменить задачей нахождения минимума, взяв коэффициенты [math]\displaystyle{ c }[/math] с обратным знаком.

Примеры задач

Максимальное паросочетание

Рассмотрим задачу о максимальном паросочетании в двудольном графе: есть несколько юношей и девушек, причём для каждых юноши и девушки известно, симпатичны ли они друг другу. Нужно поженить максимальное число пар со взаимной симпатией.

Введём переменные [math]\displaystyle{ x_{ij} }[/math], которые соответствуют паре из [math]\displaystyle{ i }[/math]-го юноши и [math]\displaystyle{ j }[/math]-й девушки и удовлетворяют ограничениям:

[math]\displaystyle{ 0\leqslant x_{ij}\leqslant 1, }[/math]

[math]\displaystyle{ x_{1j}+x_{2j}+\ldots+x_{nj}\leqslant 1, }[/math]

[math]\displaystyle{ x_{i1}+x_{i2}+\ldots+x_{im}\leqslant 1, }[/math]

с целевой функцией[math]\displaystyle{ f=c_{11}x_{11}+c_{12}x_{12}+\ldots+c_{nm}x_{nm} }[/math], где [math]\displaystyle{ c _{ij} }[/math] равны 1 или 0 в зависимости от того, симпатичны ли [math]\displaystyle{ i }[/math]-й юноша и [math]\displaystyle{ j }[/math]-я девушка друг другу. Можно показать, что среди оптимальных решений этой задачи найдётся целочисленное. Переменные, равные 1, будут соответствовать парам, которые следует поженить.

Максимальный поток

Пусть имеется граф (с ориентированными рёбрами), в котором для каждого ребра указана его пропускная способность. И заданы две вершины: сток и исток. Нужно указать для каждого ребра, сколько через него будет протекать жидкости (не больше его пропускной способности) так, чтобы максимизировать суммарный поток из истока в сток (жидкость не может появляться или исчезать во всех вершинах, кроме истока и стока, соответственно).

Возьмём в качестве переменных [math]\displaystyle{ x_i }[/math] — количество жидкости, протекающей через [math]\displaystyle{ i }[/math]-е ребро. Тогда

[math]\displaystyle{ 0\leqslant x_i\leqslant c_i, }[/math]

где [math]\displaystyle{ c_i }[/math] — пропускная способность [math]\displaystyle{ i }[/math]-го ребра. Эти неравенства надо дополнить равенством количества втекающей и вытекающей жидкости для каждой вершины, кроме стока и истока. В качестве функции [math]\displaystyle{ f }[/math] естественно взять разность между количеством вытекающей и втекающей жидкости в истоке.

Обобщение предыдущей задачи — максимальный поток минимальной стоимости. В этой задаче даны стоимости для каждого ребра и нужно среди максимальных потоков выбрать поток с минимальной стоимостью. Эта задача сводится к двум задачам линейного программирования: сначала нужно решить задачу о максимальном потоке, а потом добавить к этой задаче ограничение [math]\displaystyle{ f(x)\geqslant m }[/math], где [math]\displaystyle{ m }[/math] — величина максимального потока, и решить задачу с новой функцией [math]\displaystyle{ f(x) }[/math] — стоимостью потока.

Эти задачи могут быть решены быстрее, чем общими алгоритмами решения задач линейного программирования, за счёт особой структуры уравнений и неравенств.

Транспортная задача

Имеется некий однородный груз, который нужно перевезти с [math]\displaystyle{ n }[/math] складов на [math]\displaystyle{ m }[/math] заводов. Для каждого склада [math]\displaystyle{ i }[/math] известно, сколько в нём находится груза [math]\displaystyle{ a_i }[/math], а для каждого завода известна его потребность [math]\displaystyle{ b_j }[/math] в грузе. Стоимость перевозки пропорциональна расстоянию от склада до завода (все расстояния [math]\displaystyle{ c_{ij} }[/math] от [math]\displaystyle{ i }[/math]-го склада до [math]\displaystyle{ j }[/math]-го завода известны). Требуется составить наиболее дешёвый план перевозки.

Решающими переменными в данном случае являются [math]\displaystyle{ x_{ij} }[/math] — количества груза, перевезённого из [math]\displaystyle{ i }[/math]-го склада на [math]\displaystyle{ j }[/math]-й завод. Они удовлетворяют ограничениям:

[math]\displaystyle{ x_{i1}+x_{i2}+\ldots+x_{im}\leqslant a_i, }[/math]

[math]\displaystyle{ x_{1j}+x_{2j}+\ldots+x_{nj}\geqslant b_j. }[/math]

Целевая функция имеет вид: [math]\displaystyle{ f(x)=x_{11}c_{11}+x_{12}c_{12}+\ldots+x_{nm}c_{nm} }[/math], которую надо минимизировать.

Игра с нулевой суммой

Есть матрица [math]\displaystyle{ A }[/math] размера [math]\displaystyle{ n\times m }[/math]. Первый игрок выбирает число от 1 до [math]\displaystyle{ n }[/math], второй — от 1 до [math]\displaystyle{ m }[/math]. Затем они сверяют числа и первый игрок получает [math]\displaystyle{ a_{ij} }[/math] очков, а второй [math]\displaystyle{ (-a_{ij}) }[/math] очков ([math]\displaystyle{ i }[/math] — число, выбранное первым игроком, [math]\displaystyle{ j }[/math] — вторым). Нужно найти оптимальную стратегию первого игрока.

Пусть в оптимальной стратегии, например, первого игрока число [math]\displaystyle{ i }[/math] нужно выбирать с вероятностью [math]\displaystyle{ p_i }[/math]. Тогда оптимальная стратегия является решением следующей задачи линейного программирования:

[math]\displaystyle{ 0\leqslant p_i\leqslant 1, }[/math]

[math]\displaystyle{ p_1+\ldots+p_n=1, }[/math]

[math]\displaystyle{ a_{1i}p_1+a_{2i}p_2+\ldots+a_{ni}p_n\geqslant c\quad(i=1,\;\ldots,\;m), }[/math]

в которой нужно максимизировать функцию [math]\displaystyle{ f(p_1,\;\ldots,\;p_n,\;c)=c }[/math]. Значение [math]\displaystyle{ c }[/math] в оптимальном решении будет математическим ожиданием выигрыша первого игрока в наихудшем случае.

Алгоритмы решения

Наиболее известным и широко применяемым на практике для решения общей задачи линейного программирования (ЛП) является симплекс-метод. Несмотря на то, что симплекс-метод является достаточно эффективным алгоритмом, показавшим хорошие результаты при решении прикладных задач ЛП, он является алгоритмом с экспоненциальной сложностью. Причина этого состоит в комбинаторном характере симплекс-метода, последовательно перебирающего вершины многогранника допустимых решений при поиске оптимального решения.

Первый полиномиальный алгоритм, метод эллипсоидов, был предложен в 1979 году советским математиком Л. Хачияном, разрешившим таким образом проблему, долгое время остававшуюся нерешённой. Метод эллипсоидов имеет совершенно другую, нежели симплекс-метод, некомбинаторную природу. Однако в вычислительном плане этот метод оказался неперспективным. Тем не менее, сам факт полиномиальной сложности задач привёл к созданию целого класса эффективных алгоритмов ЛП — методов внутренней точки, первым из которых был алгоритм Н. Кармаркара, предложенный в 1984 году. Алгоритмы этого типа используют непрерывную трактовку задачи ЛП, когда вместо перебора вершин многогранника решений задачи ЛП осуществляется поиск вдоль траекторий в пространстве переменных задачи, не проходящих через вершины многогранника. Метод внутренних точек, который, в отличие от симплекс-метода, обходит точки из внутренней части области допустимых значений, использует методы логарифмических барьерных функций нелинейного программирования, разработанные в 1960-х годах Фиако (Fiacco) и МакКормиком (McCormick).

Еще один метод решения ЛП - использование алгоритма Зейделя:

1. Дана ЛП в канонической форме с [math]\displaystyle{ d }[/math] переменными и [math]\displaystyle{ m }[/math] ограничениями, составляющими множество [math]\displaystyle{ H }[/math].
2. Если [math]\displaystyle{ d = 1 }[/math] или [math]\displaystyle{ m = 0 }[/math], выведи оптимальное базисное решение [math]\displaystyle{ H }[/math].
3. Иначе выбери случайное ограничение [math]\displaystyle{ h \in H }[/math] и рекурсивно рассчитай оптимальное базисное решение для [math]\displaystyle{ H \setminus \{h\} }[/math].
4. Если оптимальное базисное решение для [math]\displaystyle{ H \setminus \{h\} }[/math] не нарушает ограничение [math]\displaystyle{ h }[/math], верни его.
5. Иначе рассчитай пересечение полиэдра ЛП с гиперплоскостью [math]\displaystyle{ h }[/math] и рекурсивно реши получившуюся ЛП с [math]\displaystyle{ d-1 }[/math] переменной.

Данный метод имеет асимтотическую сложность [math]\displaystyle{ O(m \cdot d!) }[/math].

Двойственные задачи линейного программирования

Каждой задаче линейного программирования вида

[math]\displaystyle{ \sum_{j=1}^n a_{ij}x_j\leqslant c_i,\;i=\overline{1,\;m}; }[/math]

[math]\displaystyle{ x_j\geqslant 0,\;j=\overline{1,\;n}; }[/math]

[math]\displaystyle{ F(x)=\sum_{j=1}^n b_jx_j\to\max }[/math]

можно определённым образом сопоставить некоторую другую задачу линейного программирования, называемую двойственной или сопряжённой по отношению к исходной или прямой. Связь исходной и двойственной задач заключается главным образом в том, что решение одной из них может быть получено непосредственно из решения другой. Дадим определение двойственной задачи по отношению к исходной задаче линейного программирования

Исходная задача	Двойственная задача
[math]\displaystyle{ \sum_{j=1}^n a_{ij}x_j\leqslant c_i,\;i=\overline{1,\;m} }[/math]	[math]\displaystyle{ y_i\geqslant 0,\;i=\overline{1,\;m} }[/math]
[math]\displaystyle{ x_j\geqslant 0,\;j=\overline{1,\;n} }[/math]	[math]\displaystyle{ \sum_{i=1}^m a_{ij}y_i\geqslant b_j,\;j=\overline{1,\;n} }[/math]
[math]\displaystyle{ F(x)=\sum_{j=1}^n b_jx_j\to\max }[/math]	[math]\displaystyle{ T(y)=\sum_{i=1}^m c_iy_i\to\min }[/math]

Если вектора [math]\displaystyle{ x }[/math] и [math]\displaystyle{ y }[/math] — допустимые решения прямой и двойственной задачи, то [math]\displaystyle{ F(x)\leqslant T(y) }[/math], причём равенство достигается тогда и только тогда, когда [math]\displaystyle{ x }[/math] и [math]\displaystyle{ y }[/math] — оптимальные решения. Если же целевая функция одной из пары двойственных задач не ограничена (для исходной — сверху, для двойственной — снизу), то область допустимых решений другой задачи — пустая.

Если вектора [math]\displaystyle{ x^* }[/math] и [math]\displaystyle{ y^* }[/math] — оптимальные решения прямой и двойственной задачи, соответственно, то верны следующие равенства

[math]\displaystyle{ x_j^*(\sum_{i=1}^m a_{ij} y_i^*-b_j)=0,\;j=\overline{1,\;n}; }[/math]

[math]\displaystyle{ y_i^*(\sum_{j=1}^n a_{ij} x_j^*-c_i)=0,\;i=\overline{1,\;m}. }[/math]

То есть, для оптимальных решений прямой и двойственной задачи, ненапряженным (выполняется строгое неравенство) ограничениям соответствуют нулевые переменные, а ненулевым переменным (входящим в опорный план) соответствуют напряжённые (нестрогое неравенство реализуется, как равенство) ограничения. Но могут быть и нулевые переменные, соответствующие напряжённым ограничениям.

Эти свойства двойственных решений позволяют существенно сократить время решения, если приходится решать задачу, с числом ограничений много большим количества переменных. Тогда можно, решив двойственную задачу, найти её опорный план, после чего, отобрав в прямой задаче только ограничения, соответствующие опорному плану (все эти ограничения должны быть напряжены), решить для них обычную систему линейных уравнений.

Теорема. Двойственная двойственной задачи ЛП является прямая задача ЛП.

Доказательство: Рассмотрим прямую ЛП вида [math]\displaystyle{ \max c^T }[/math] при условии [math]\displaystyle{ Ax \leqslant b, x \geqslant 0 }[/math]. Сопоставим ей двойственную ЛП и получим [math]\displaystyle{ \min b^Ty }[/math] при условии [math]\displaystyle{ A^Ty \geqslant c, y \geqslant 0 }[/math]. Приведем ее к другой форме, эквивалентной по смыслу: [math]\displaystyle{ \max -b^Ty }[/math] при условии [math]\displaystyle{ -A^Ty \leqslant -c, y \geqslant 0 }[/math]. Вновь сопоставим ей двойственную ЛП и получим [math]\displaystyle{ \min -c^Tx }[/math] при условии [math]\displaystyle{ -Ax \geqslant -b, x \geqslant 0 }[/math]. Приведем ее в эквивалентную форму и получим ЛП идентичную исходной: [math]\displaystyle{ \max c^T }[/math] при условии [math]\displaystyle{ Ax \leqslant b, x \geqslant 0 }[/math].

Программное обеспечение

lp_solve — открытое программное обеспечение (лицензия LGPL GNU Стандартная общественная лицензия GNU для библиотек) для решения линейных уравнений. LpSolve имеет IDE, собственный C API, и множество других программных интерфейсов для Java, AMPL, MATLAB, Wolfram Mathematica, O-Matrix, Sysquake, Scilab, Octave, FreeMat, Euler, Python, Sage, PHP, R и Microsoft Solver Foundation.

См. также

• Нелинейное программирование
• Алгоритм Данцига
• Графический метод решения задачи линейного программирования
• Дробно-линейное программирование
• Модель «затраты — выпуск»

Литература

• Абрамов Л. М., Капустин В. Ф. Математическое программирование. — Учебное пособие. — Л.: ЛГУ, 1981. — 328 с.
• Акоф Р., Сасиени М. Основы исследования операций. — Пер. с англ. В. Я. Алтаева., под ред. И. А. Ушакова. — М.: Мир, 1971. — 551 с.
• Акулич И. Л. Глава 1. Задачи линейного программирования, Глава 2. Специальные задачи линейного программирования // Математическое программирование в примерах и задачах. — М.: Высшая школа, 1986. — 319 с. — ISBN 5-06-002663-9.
• Астафьев Н. Н. Бесконечные системы линейных неравенств в математическом программировании. — М.: Наука, 1991. — 134 с.
• Ашманов С. А., Тимохов А. В. Теория оптимизации в задачах и упражнениях. — М.: Наука, 1991. — 446 с.
• Гасс С. Линейное программирование. — М.: Физико-математическая литература, 1961. — 300 с.
• Давыдов Э. Г. Исследование операций. — М.: Высшая школа, 1990. — 382 с.
• Дегтярёв Ю. И. Исследование операций. — Учебник для вузов. — М.: Высшая школа, 1986. — 320 с.
• Зуховицкий С. И., Авдеева Л. И. Линейное и выпуклое программирование. — М.: Наука, 1966. — 348 с.
• Карманов В. Г. Математическое программирование. — 3-е издание. — М.: Наука, 1986. — 288 с.
• Кузнецов А. В., Сакович В. А., Холод Н. И. Высшая математика. Математическое программирование. — Минск.: Вышейшая школа, 1994. — 286 с.
• Томас Х. Кормен и др. Глава 29. Линейное программирование // Алгоритмы: построение и анализ = Introduction to Algorithms. — 2-е изд. — М.: «Вильямс», 2006. — С. 1296. — ISBN 5-8459-0857-4.
• Юдин Д. Б., Гольштейн Е. Г. Линейное программирование. — М.: Наука, 1969. — 424 с.
• Данциг Дж. Б. Воспоминания о начале линейного программирования.
• Габасов Р., Кириллова Ф. М. Методы линейного программирования. — Минск: БГУ, 1977. — 176 с.

Ссылки

• Linear Program Solver (LiPS) — Бесплатный оптимизационный пакет, предназначенный для решения задач линейного, целочисленного и целевого программирования.
• Вершик А. М. O Л. В. Канторовиче и линейном программировании
• Слайды по линейному программированию
• Большакова И. В., Кураленко М. В. Линейное программирование. Учебно-методическое пособие к контрольной работе.  (недоступная ссылка с 13-05-2013 [4044 дня])
• Барсов А. С. Что такое линейное программирование // Популярные лекции по математике, Гостехиздат, 1959.
• Вялый М. Н. Линейные неравенства и комбинаторика. — МЦНМО, 2003.